#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define vec vector<int>
#define y1 y_____hahahaha_____1
#define count __builtin_popcount

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

int read(){int x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); return x * sgn;}

const int S = 1 << 15;
const int N = 55;
const int mod = 1000003;

int cnt[N],n,k,f[2][S],l;
char s[N][N];

void upd(int &x){x = x + (x >> 31 & mod);}

void solve(){
	n = in,k = in; memset(f,0,sizeof f); int U = 1 << n;
	f[0][U - 1] = 1; int o = 0;
	for(int i = 1;i <= n;i++) scanf("%s",s[i] + 1); l = strlen(s[1] + 1);
	for(int i = 1;i <= l;i++,o ^= 1){
		memset(f[o ^ 1],0,sizeof f[o ^ 1]);
		int numa = 0;
		for(int j = 0;j < 26;j++) cnt[j] = 0;
		for(int j = 1;j <= n;j++) if(s[j][i] != '?') cnt[s[j][i] - 'a'] |= 1 << j - 1; else numa |= 1 << j - 1;
		for(int j = 0;j < 26;j++) cnt[j] |= numa;
		for(int s = 0;s < U;s++){
			if(count(s) < k) continue; if(!f[o][s]) continue;
			for(int j = 0;j < 26;j++){
				upd(f[o ^ 1][s & cnt[j]] += f[o][s] - mod);
			}
		}
	}
	int ans = 0;
	for(int s = 0;s < U;s++) if(count(s) == k) upd(ans += f[o][s] - mod);
	printf("%d\n",ans);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	for(int t = in;t;t--) solve();	
	return 0;
}
